Here is Shaoyu

Probabilistic Graphical Model

2022/05/16 10:28:00 2022/05/17 09:00:00 Bayesian Belief Propagation Markov Random Field

本文主要梳理建立在概率图模型上的多种概念，及其相关的算法。

1. 概率图模型

概率图模型 (Probabilistic Graphical Model) 是一种表示随机变量之间条件依赖的结构。使用概率图模型的动机在于——利用基于图的表示对多维空间上的概率分布进行编码。对于特定分布中的一组独立性 (independency) ，图结构是这种独立性的紧凑表示、或分解表示[1]。

即：

对于一个多元的分布，可以通过不同的诱导方式将其表征为图模型。
一个多元分布可以根据已有的概率图模型上的连接，做关系分解。

概率图模型的分类如下 (尚不完整) ：

有向图模型
- 有向无环图 (贝叶斯网络，Bayesian Network)
- 循环有向图模型
无向图模型 (随机场模型)
- 马尔可夫随机场 (Markov Random Field)
- 条件随机场 (Conditional Random fields)
因子图 (Factor Graph)

1.1 贝叶斯网络 (Bayesian Model)

又名：Bayes network, Bayes net, belief network, or decision network

贝叶斯网络是一种概率图形模型，它通过有向无环图 (Directed Acyclic Graph) 表示一组变量及其条件依赖关系。

贝叶斯网络非常适合用于获取已发生的事件并预测几种可能的已知原因中的任何一种是促成因素的可能性。例如，贝叶斯网络可以表示疾病和症状之间的概率关系。给定症状，该网络可用于计算各种疾病存在的概率[2]。

在形式上，贝叶斯网络是有向无环图，其节点与边的定义如下：

节点：代表概率意义上的变量，每个节点都与一个概率函数相关联 (以父节点变量为条件/输入，该节点为输出) 。变量类型包括

可观察的变量
潜在变量
未知的参数或者假设

边：代表条件依赖，未被连接的节点表示条件独立的变量 (两节点之间不存在任意路径)

1.2 马尔可夫随机场 (Markov Random Field)

又名：Markov Network

马尔可夫随机场是一组具有由无向图描述的，具有马尔可夫性质的随机变量。换句话说，如果随机场满足马尔可夫性质，则称其为马尔可夫随机场。

马尔可夫网络或 MRF 在其依赖关系的表示方面类似于贝叶斯网络；区别在于贝叶斯网络是有向无环的，而马尔可夫网络是无向的并且可能是循环的。因此，马尔可夫网络可以表示贝叶斯网络不能表示的某些依赖关系 (例如循环依赖关系，cyclic dependencies) ；另一方面，它不能表示贝叶斯网络可以表示的某些依赖关系 (例如诱导依赖关系，induced dependencies) 。马尔可夫随机场的基础图可能是有限的或无限的。

1.2.1 定义

马尔可夫性质

给定一个无向图$G=(V,E)$，一系列随机变量$X = (X_v)_{v \in V}$，当随机变量满足以下性质时，我们称他们相对于$G$形成了一个马尔可夫随机场。
1. 成对马尔可夫性质 (Pairwise Markov property) ：给定所有的其他变量，任何两个在图上不相邻的变量都是条件独立的。即：$X_{u} \perp X_{v} \mid X_{V \backslash{u, v}}$
2. 局部马尔可夫性质 (Local Markov property) ：一个变量在给定其邻居的情况下，条件独立于所有其他变量。即：$X_{v} \perp X_{V \backslash \mathrm{N}[v]} \mid X_{\mathrm{N}(v)}$，$\mathrm{N}[v]$是$v$的邻居集合，$\mathrm{N}[v]=v \cup \mathrm{N}(v)$是节点$v$的closed neighborhood。
3. 全局马尔可夫性质 (Global Markov property) ：给定一个分离子集，任何两个变量子集都是条件独立的。即：$X_{A} \perp X_{B} \mid X_{S}$，其任意从$A$中的节点到$B$中的节点的路径，都经过子集$S$。
属性强弱：Global Markov property > Local Markov property > Pairwise Markov property。上述三个马尔可夫性质对于正分布 (那些只为相关变量分配非零概率的分布) 是等价的。
随机场：当给图中的每一个变量，都按照某种分布随机赋予相空间 (phase space) 的一个值之后，其构成的全体就叫做随机场。

1.3 因子图 (Factor Graph)

因子图 (Factor Graph) 是表示函数分解的二分图。在概率论及其应用中，因子图用于表示概率分布函数的因式分解，从而实现高效计算，例如通过sum-product 算法计算边缘分布。

1.3.1 定义

因子图是一种二部图，用于表示联合概率分布的函数分解，以如下的联合概率为例：

$$ g\left(X_{1}, X_{2}, \ldots, X_{n}\right)=\prod_{j=1}^{m} f_{j}\left(S_{j}\right) $$

其中$g\left(X_{1}, X_{2}, \ldots, X_{n}\right)$是联合概率分布，默认为实值函数。$S_j\subseteq\left\{X_{1}, X_{2}, \ldots, X_{n}\right\}$，即$S_j$是变量节点的一个子集。

上式对应的因子图表示为$G = (X, F, E)$，其中$X={X_1, X_2, \cdots, X_n}$，表示变量节点构成的集合；$F={f_1, f_2, \cdots f_m}$表示因子节点构成的集合。因子图上的边$E$定义在因子节点与变量节点之间，即因子节点$f_j$与变量节点$X_k, X_k \in S_j$之间存在一条无向的边。

举例：

上图描述了如下概率分布的分解 (该图是一个有环图的特例) ：

$$ g\left(X_{1}, X_{2}, X_{3}\right)=f_{1}\left(X_{1}\right) f_{2}\left(X_{1}, X_{2}\right) f_{3}\left(X_{1}, X_{2}\right) f_{4}\left(X_{2}, X_{3}\right) $$

1.3.2 联系

无论是有向概率图模型还是无向概率图模型，他们都能使用因子图来描述。因为因子节点 (factor) 理论上可以描述变量之间的任何定义在实数域上的函数关系，还摆脱了probability function的取值必须为$[0,1]$的限制，因此使用因子图表示的概率图模型可以实现高效、统一的计算。

2. 算法

2.1 消息传递算法 (Massage Passing Algorithm)

推断 (inference) 是概率图模型上的一个重要任务，简单来讲就是已知一系列条件概率函数，求每个随机变量的边缘概率。

直接地，解上述问题可以有两种思路：

采用解析的方式，利用贝叶斯法则求边缘概率，但这种方法的复杂度随变量规模呈指数增加[3]。
采用模拟的方法，让消息按照概率图模型进行传递，在迭代$N$次后分析消息的传递效果。

后者由于简单的思路与计算复杂度，具有较高的实用性，因此被广泛使用，这类方法被称为消息传递算法。

关于消息传递，这篇blog做了详细的阐述，可以参考。

2.1.1 置信传播算法 (Belief propagation)

又名：sum–product message passing

置信传播算法 (Belief propagation) ，是一种消息传递算法 (message passing algorithm) ，用于对图模型 (例如贝叶斯网络和马尔可夫随机场) 进行推理。它以任何观察到的节点 (或变量) 为条件，计算每个未观察到的节点 (或变量) 的边缘分布。

BP算法在贝叶斯网络与马尔可夫随机场上都有相关的变体，但由于上述两张图模型都可以使用因子图来描述，因此后文直接叙述BP算法在因子图上的计算方法。

2.1.1.1 算法描述

给定因子图$G=(V, F, E)$，有联合质量函数$p(\mathbf{x})=\prod_{a \in F} f_{a}\left(\mathbf{x}{a}\right)$，其中$\mathbf{x}{a}$是因子节点$a$的所有邻居变量节点所构成的向量。注：联合质量函数 (Joint mass function) 是变量在每个可能的值上取得该值的概率，不同于概率密度函数，概率质量函数是在离散随机变量上定义的，而概率密度函数是在连续随机变量上定义的。

BP算法的原理在于，让被称为消息 (Message) 的实值函数沿着概率图中隐藏节点之间的边进行传递。具体而言包含两种情况，其中$\operatorname{Dom}(v)$表示变量$v$的定义域。

从变量节点$v$到因子节点$a$的传递，记传递的消息为$\mu_{v \to a}$，$\mu_{v \rightarrow a}: \operatorname{Dom}(v) \rightarrow \mathbb{R}$。
从因子节点$a$到变量节点$v$的传递，记为$\mu_{a \to v}$，$\mu_{a \rightarrow v}: \operatorname{Dom}(v) \rightarrow \mathbb{R}$。

BP算法中对于上述两种消息的传递，定义不同的计算方式

对于从变量节点到因子节点的消息传递$\mu_{v \to a}$
$$ \mu_{v \rightarrow a}\left(x_{v}\right)=\prod_{a^{*} \in N(v) \backslash\{a\}} \mu_{a^{*} \rightarrow v}\left(x_{v}\right) $$
其中$x_{v} \in \operatorname{Dom}(v)$，$N(v)$是节点$v$的邻居节点，如果$N(v) \backslash\{a\} = \emptyset$，则上式被置为均匀分布。
对于从因子节点到变量节点的消息传递$\mu_{a \to v}$被定义为因子与来自所有其他节点的消息的乘积，除与$v$相关的变量外，所有变量都被边缘化 (marginalized)
$$ \mu_{a \rightarrow v}\left(x_{v}\right)=\sum_{\mathbf{x}_{a}^{\prime}: x_{v}^{\prime}=x_{v}} f_{a}\left(\mathbf{x}_{a}^{\prime}\right) \prod_{v^{*} \in N(a) \backslash\{v\}} \mu_{v^{*} \rightarrow a}\left(x_{v^{*}}^{\prime}\right) $$
其中$x_{v} \in \operatorname{Dom}(v)$，$N(a)$是节点$a$的邻居节点，如果$N(a) \backslash{v} = \emptyset$，则$\mu_{a \rightarrow v}\left(x_{v}\right)=f_{a}\left(x_{v}\right)$

由上式可以看出，BP算法将完全边缘化计算 (complete marginalization) 简化为了更简单的项的乘积和，这也是BP算法被称为sum-product message passing或sum-product algorithm的原因。

在典型的运行情况中，每条消息都将从相邻消息的先前值上迭代更新。可以使用不同的调度策略来更新消息。在图模型是树的情况下，最优调度允许在只计算每条消息一次后达到收敛。当因子图有循环时，这样的最优调度是不存在的，典型的选择是在每次迭代时同时更新所有消息。